// #include <stdio.h>
// #include <stdlib.h>

// #define MAX_N 21
// #define MAX_C 1001

// int main() 
// {
//     int c, n;
//     scanf("%d %d", &c, &n);
    
//     int weight[MAX_N], value[MAX_N];
    
//     // 读取重量
//     for (int i = 1; i <= n; i++) 
//     {
//         scanf("%d", &weight[i]);
//     }
    
//     // 读取价值
//     for (int i = 1; i <= n; i++) 
//     {
//         scanf("%d", &value[i]);
//     }
    

    
//     /*这里才是关键部分*/
 



//     // dp数组，记录最大价值
//     int dp[MAX_N][MAX_C] = {0};
//     // path数组，记录选择路径
//     int path[MAX_N][MAX_C] = {0};
    
//     // 这里我可以理解，第一列的时候，因为背包容量是0，因此直接初始化为0即可
//     // 

//     // 动态规划求解
//     for (int i = 1; i <= n; i++) 
//     {
//         for (int j = 0; j <= c; j++) 
//         {
//             // 这里的j是背包容量，然后看j是否比尝试装入的物品更重
//             if (j >= weight[i]) 
//             {
//                 // 当前放入物品时，比较一下当前重量下，上一个的价值总和，与上一个状态下抛弃这个
//                 if (dp[i-1][j] < dp[i-1][j - weight[i]] + value[i]) 
//                 {
//                     dp[i][j] = dp[i-1][j - weight[i]] + value[i];
//                     path[i][j] = 1;  // 选择当前物品
//                 } 
//                 else 
//                 {
//                     dp[i][j] = dp[i-1][j];
//                     path[i][j] = 0;  // 不选择当前物品
//                 }

//                 // 这里可以改写为三目运算符
//                 // 原来是打字太飘了吧还是电池没电了/？？？？？
//             } 
//             else 
//             {
//                 dp[i][j] = dp[i-1][j];
//                 path[i][j] = 0;
//             }
//         }
//     }
    
//     // 回溯找出选择的物品
//     int selected[MAX_N] = {0};
//     int total_weight = 0;
//     int count = 0;
    
//     int j = c;
//     for (int i = n; i >= 1; i--) 
//     {
//         if (path[i][j] == 1) 
//         {
//             selected[count++] = i;
//             total_weight += weight[i];
//             j -= weight[i];
//         }
//     }
    
//     // 输出结果
//     // 输出选择的物品序号（从小到大）
//     for (int i = count - 1; i >= 0; i--) 
//     {
//         printf("%d", selected[i]);
//         if (i > 0) printf(" ");
//     }
//     printf(" %d %d\n", total_weight, dp[n][c]);
    
//     return 0;
// }

#include <stdio.h>
#include <stdlib.h>

// 求两个数的最大值
int max(int a, int b) 
{
    return a > b ? a : b;
}


// 01背包问题 - 一维数组解法
int knapsack_01(int capacity, int weights[], int values[], int n) 
{
    // 创建并初始化dp数组
    int *dp = (int *)malloc((capacity + 1) * sizeof(int));
    
    // 初始化dp数组，容量为0时价值为0
    for (int j = 0; j <= capacity; j++) 
    {
        dp[j] = 0;
    }
    
    // ****手写vector容器来记录到底是谁
    int arr[10000];
    int back = 0;      // 我就不用迭代器了，这里毕竟可以下标说话
    
    // 动态规划过程
    for (int i = 0; i < n; i++) 
    {
        // 逆序遍历容量，防止重复选择同一物品
        for (int j = capacity; j >= weights[i]; j--) 
        {
            // 现在我要对这个大下标的部分进行重新赋值
            // j-weights[i] 表示假设我的背包在小下标的位置已经有了一个最大值，
            // 现在我要往里加入当前待放入物品了，看看是:
            // (1) 这个恰好能放入的物品加上没放之前的
            // (2) 原本之前有过的值，也就是之前dp过的值
            // 这两个到底谁更大？？？
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);

            // 相当于每次我都在尝试更新数组中的每一个元素
            // 第一次全是0，因此第一次的第一个dp[capacity]肯定会被赋值为values[i]   
            // 但是这只是中间过程，第二次进行数组滚动的时候

            // (一下部分定义了一个会像浪花一样沿数组向遍历方向移动的dp法则，以此来解释为什么不能正向遍历)
            // 在之前状态改变方程的动态项位置的值发生了变化
            // 也就是"放入物品之前"的状态有可能变大了，因此这次才是真正的比较:
            // j-weight[i] 位置已经有了重量小物体A，现在往里加入了重量小物体B
            // 而j位置处，是原本第一次循环放入的重量大物体C
            // 也就是要让C的价值与A的价值加上B的价值进行比较，并使用最大值对dp[j]进行重新赋值
            
            // ****上述dp法则会作用于每一次程序运行中数组中所有位置对应的元素
            // ****它们都会依照上述法则进行变化，就像浪花一样，从j往j-1作用，而本次外层循环j位置不会再受影响

        }
        
        // 调试输出：显示每步处理后的dp数组
        // printf("处理第%d个物品(重量:%d, 价值:%d)后: ", i+1, weights[i], values[i]);
        // for (int j = 0; j <= capacity; j++) 
        // {
        //     printf("%d ", dp[j]);
        // }
        // printf("\n");
    }
    
    // 容量为capacity位置处当然就是结果了，这就有点像利用单位矩阵求逆矩阵一样
    // AE ----------> EA^-1
    int result = dp[capacity];

    // ****开辟完的空间一旦不再使用必须要进行释放
    // ****短期之内看不到危害，但是等你写起程序你就知道什么情况了
    free(dp);
    dp = NULL;      // 我觉得free一个指针后还需要滞空一下，不是我觉得，而是一个好习惯
    return result;
}

// 带路径回溯的01背包
// void knapsack_with_trace(int capacity, int weights[], int values[], int n) {
//     int *dp = (int *)malloc((capacity + 1) * sizeof(int));
//     int **path = (int **)malloc(n * sizeof(int *));
    
//     for (int i = 0; i < n; i++) {
//         path[i] = (int *)malloc((capacity + 1) * sizeof(int));
//     }
    
//     // 初始化
//     for (int j = 0; j <= capacity; j++) {
//         dp[j] = 0;
//         for (int i = 0; i < n; i++) {
//             path[i][j] = 0;
//         }
//     }
    
//     // 动态规划
//     for (int i = 0; i < n; i++) {
//         for (int j = capacity; j >= weights[i]; j--) {
//             if (dp[j] < dp[j - weights[i]] + values[i]) {
//                 dp[j] = dp[j - weights[i]] + values[i];
//                 path[i][j] = 1; // 标记选择了该物品
//             }
//         }
//     }
    
//     // 输出结果
//     printf("\n最大价值: %d\n", dp[capacity]);
//     printf("选择的物品: ");
    
//     int remaining_capacity = capacity;
//     for (int i = n - 1; i >= 0; i--) {
//         if (path[i][remaining_capacity] == 1) {
//             printf("物品%d(重量:%d, 价值:%d) ", i+1, weights[i], values[i]);
//             remaining_capacity -= weights[i];
//         }
//     }
//     printf("\n");
    
//     // 释放内存
//     free(dp);
//     for (int i = 0; i < n; i++) {
//         free(path[i]);
//     }
//     free(path);
// }

int main() {
    // 测试数据
    int capacity = 10; // 背包容量
    int weights[] = {2, 3, 4, 5}; // 物品重量
    int values[] = {3, 4, 5, 6};  // 物品价值
    int n = sizeof(weights) / sizeof(weights[0]);
    
    printf("背包容量: %d\n", capacity);
    printf("物品信息:\n");
    for (int i = 0; i < n; i++) {
        printf("物品%d: 重量=%d, 价值=%d\n", i+1, weights[i], values[i]);
    }
    
    printf("\n=== 基础解法 ===\n");
    int max_value = knapsack_01(capacity, weights, values, n);
    printf("\n最大价值: %d\n", max_value);
    
    // printf("\n=== 带路径回溯的解法 ===\n");
    // knapsack_with_trace(capacity, weights, values, n);
    
    return 0;
}